package com.javabasic.algorithm.sword_of_offer;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/19 12:17 上午
 */
public class 剑指_Offer_12_矩阵中的路径 {

    int[][] NEXT = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int NEXT_LEN = 4;
    int[][] unVisit;

    public boolean exist(char[][] board, String word) {
        int len = word.length();
        int lenx = board.length;
        int leny = board[0].length;
        unVisit = new int[lenx][leny];
        int tag = 1;
        for (int i = 0; i < lenx; i++) {
            for (int j = 0; j < leny; j++) {
                unVisit[i][j] = tag;
                if (dfs(i, j, lenx, leny, board, 0, len, word, tag)) {
                    return true;
                }
                tag++;
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, int lenx, int leny, char[][] board, int index, int len, String word, int tag) {
        int tempx, tempy;

        if (board[x][y] == word.charAt(index)) {
            if (index == len-1) {
                return true;
            }
        } else {
            return false;
        }

        for (int k = 0; k < NEXT_LEN; k++) {
            tempx = x + NEXT[k][0];
            tempy = y + NEXT[k][1];
            if (validCoordination(tempx, tempy, lenx, leny, tag)) {
                unVisit[tempx][tempy] = tag;
                if (dfs(tempx, tempy, lenx, leny, board, index + 1, len, word, tag)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean validCoordination(int tempx, int tempy, int m, int n, int tag) {
        if (tempx < 0 || tempx >= m || tempy < 0 || tempy >= n || unVisit[tempx][tempy] == tag) {
            return false;
        }
        return true;
    }
}
